An existing checksum technique used for tampering detection is the one described in Non-patent literature 1. The checksum technique described in Non-patent literature 1 includes addition and multiplication and can be efficiently applied to secure computation.
The checksum technique described in Non-patent literature 1 uses random numbers r∈F to generate a check sum c of values a0, . . . , aN−1∈F according to Formula 1 given below, where F is a field.
                    c        :=                              ∑                          0              ≤              i              <              N                                ⁢                                    a              i                        ⁢                          r                              i                +                1                                                                        [                  Formula          ⁢                                          ⁢          1                ]            
In Non-patent literature 1, the checksum c is verified according to Formula 2 given below.
                                          ∑                          0              ≤              i              <              N                                ⁢                                    a              i                        ⁢                          r                              i                +                1                                                    -        c                            [                  Formula          ⁢                                          ⁢          2                ]            
If Formula 2 yields 0, then it is determined that none of the values a0, . . . , aN−1 have been tampered with. If Formula 2 yields a value other than 0, it is determined that at least one of the values a0, . . . , aN−1 has been tampered with.